home *** CD-ROM | disk | FTP | other *** search
/ The Fatted Calf / The Fatted Calf.iso / Unix / Shells / zsh / Source / src / table.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-04-07  |  7.3 KB  |  377 lines
  1. /*
  2.  *
  3.  * table.c - linked lists and hash tables
  4.  *
  5.  * This file is part of zsh, the Z shell.
  6.  *
  7.  * This software is Copyright 1992 by Paul Falstad
  8.  *
  9.  * Permission is hereby granted to copy, reproduce, redistribute or otherwise
  10.  * use this software as long as: there is no monetary profit gained
  11.  * specifically from the use or reproduction of this software, it is not
  12.  * sold, rented, traded or otherwise marketed, and this copyright notice is
  13.  * included prominently in any copy made.
  14.  *
  15.  * The author make no claims as to the fitness or correctness of this software
  16.  * for any use whatsoever, and it is provided as is. Any use of this software
  17.  * is at the user's own risk.
  18.  *
  19.  */
  20.  
  21. #define TABLE_C
  22. #include "zsh.h"
  23.  
  24. /* get an empty linked list header */
  25.  
  26. Lklist newlist()
  27. {                /**/
  28.     Lklist list;
  29.  
  30.     list = (Lklist) alloc(sizeof *list);
  31.     list->first = 0;
  32.     list->last = (Lknode) list;
  33.     return list;
  34. }
  35.  
  36. /* get an empty hash table */
  37.  
  38. Hashtab newhtable(size)        /**/
  39. int size;
  40. {
  41.     Hashtab ret;
  42.  
  43.     ret = (Hashtab) zcalloc(sizeof *ret);
  44.     ret->hsize = size;
  45.     ret->nodes = (Hashnode *) zcalloc(size * sizeof(Hashnode));
  46.     return ret;
  47. }
  48.  
  49. /* the hash function used by Chris Torek */
  50. /* The Peter J. Weinberger hash function from the Dragon Book
  51.  * used to be here but it
  52.  * a) was slower than this
  53.  * b) took 32-bit integers for granted
  54.  *    b1) there are other integer widths
  55.  *    b2) integer constant like 0xf0000000 is unsigned in ANSI C,
  56.  *        signed with pcc
  57.  * c) I _believe_ after some testing that this hashes better
  58.  *    Jarkko Hietaniemi <Jarkko.Hietaniemi@hut.fi>
  59.  */
  60.  
  61. unsigned hasher(s)            /**/
  62. char *s;
  63. {
  64.     unsigned hash;
  65.  
  66.     for (hash = 0; *s; s++)
  67.     hash = hash + (hash << 5) + *s;
  68.     /* if hashing counted strings: (size_t, char *) pairs,
  69.      * "+ 1" should be appended to the above line */
  70.  
  71.     return hash;
  72. }
  73.  
  74. /* add a node to a hash table */
  75.  
  76. void addhnode(nam, dat, ht, freefunc)    /**/
  77. char *nam;
  78. vptr dat;
  79. Hashtab ht;
  80. FFunc freefunc;
  81. {
  82.     int hval = hasher(nam) % ht->hsize;
  83.     struct hashnode **hp = ht->nodes + hval, *hn;
  84.  
  85.     for (; *hp; hp = &(*hp)->next)
  86.     if (!strcmp((*hp)->nam, nam)) {
  87.         zsfree((*hp)->nam);
  88.         hn = (struct hashnode *)dat;
  89.         hn->next = (*hp)->next;
  90.         if (!freefunc)
  91.         zerr("attempt to call NULL freefunc", NULL, 0);
  92.         else
  93.         freefunc(*hp);
  94.         *hp = hn;
  95.         hn->nam = nam;
  96.         return;
  97.     }
  98.     hn = (Hashnode) dat;
  99.     hn->nam = nam;
  100.     hn->next = ht->nodes[hval];
  101.     ht->nodes[hval] = hn;
  102.     if (++ht->ct == ht->hsize * 4)
  103.     expandhtab(ht);
  104. }
  105.  
  106. /* add a node to command hash table */
  107.  
  108. void addhcmdnode(nam, pnam)    /**/
  109. char *nam;
  110. char **pnam;
  111. {
  112.     int hval = hasher(nam) % cmdnamtab->hsize;
  113.     struct hashnode *hp = cmdnamtab->nodes[hval], *hn;
  114.     Cmdnam cc;
  115.  
  116.     for (; hp; hp = hp->next)
  117.     if (!strcmp(hp->nam, nam))
  118.         return;
  119.     cc = (Cmdnam) zcalloc(sizeof *cc);
  120.     cc->flags = EXCMD;
  121.     cc->u.name = pnam;
  122.     hn = (Hashnode) cc;
  123.     hn->nam = ztrdup(nam);
  124.     hn->next = cmdnamtab->nodes[hval];
  125.     cmdnamtab->nodes[hval] = hn;
  126.     if (++cmdnamtab->ct == cmdnamtab->hsize * 4)
  127.     expandhtab(cmdnamtab);
  128. }
  129.  
  130. /* expand hash tables when they get too many entries */
  131.  
  132. void expandhtab(ht)        /**/
  133. Hashtab ht;
  134. {
  135.     struct hashnode **arr, **ha, *hn, *hp;
  136.     int osize = ht->hsize, nsize = osize * 8, os = osize;
  137.  
  138.     ht->hsize = nsize;
  139.     arr = ht->nodes;
  140.     ht->nodes = (Hashnode *) zcalloc(nsize * sizeof(struct hashnode *));
  141.  
  142.     ht->ct = 0;
  143.  
  144.     for (ha = arr; osize; osize--, ha++)
  145.     for (hn = *ha; hn;) {
  146.         hp = hn->next;
  147.         addhnode(hn->nam, (vptr) hn, ht, (FFunc) 0);
  148.         hn = hp;
  149.     }
  150.     zfree(arr, os * sizeof(struct hashnode *));
  151. }
  152.  
  153. /* get an entry in a hash table */
  154.  
  155. vptr gethnode(nam, ht)        /**/
  156. char *nam;
  157. Hashtab ht;
  158. {
  159.     int hval = hasher(nam) % ht->hsize;
  160.     struct hashnode *hn = ht->nodes[hval];
  161.  
  162.     for (; hn; hn = hn->next)
  163.     if (!strcmp(hn->nam, nam))
  164.         return (vptr) hn;
  165.     return NULL;
  166. }
  167.  
  168. void freehtab(ht, freefunc)    /**/
  169. Hashtab ht;
  170. FFunc freefunc;
  171. {
  172.     int val;
  173.     struct hashnode *hn, **hp = &ht->nodes[0], *next;
  174.  
  175.     for (val = ht->hsize; val; val--, hp++)
  176.     for (hn = *hp; hn;) {
  177.         next = hn->next;
  178.         zsfree(hn->nam);
  179.         freefunc(hn);
  180.         hn = next;
  181.     }
  182.     zfree(ht->nodes, ht->hsize * sizeof(struct hashnode *));
  183.     zfree(ht, sizeof(struct hashtab));
  184. }
  185.  
  186. /* remove a hash table entry and return a pointer to it */
  187.  
  188. vptr remhnode(nam, ht)        /**/
  189. char *nam;
  190. Hashtab ht;
  191. {
  192.     int hval = hasher(nam) % ht->hsize;
  193.     struct hashnode *hn = ht->nodes[hval], *hp;
  194.  
  195.     if (!hn)
  196.     return NULL;
  197.     if (!strcmp(hn->nam, nam)) {
  198.     ht->nodes[hval] = hn->next;
  199.     zsfree(hn->nam);
  200.     ht->ct--;
  201.     return (vptr) hn;
  202.     }
  203.     for (hp = hn, hn = hn->next; hn; hn = (hp = hn)->next)
  204.     if (!strcmp(hn->nam, nam)) {
  205.         hp->next = hn->next;
  206.         zsfree(hn->nam);
  207.         ht->ct--;
  208.         return (vptr) hn;
  209.     }
  210.     return NULL;
  211. }
  212.  
  213. /* insert a node in a linked list after 'llast' */
  214.  
  215. void insnode(list, llast, dat)    /**/
  216. Lklist list;
  217. Lknode llast;
  218. vptr dat;
  219. {
  220.     Lknode tmp;
  221.  
  222.     tmp = llast->next;
  223.     llast->next = (Lknode) alloc(sizeof *tmp);
  224.     llast->next->last = llast;
  225.     llast->next->dat = dat;
  226.     llast->next->next = tmp;
  227.     if (tmp)
  228.     tmp->last = llast->next;
  229.     else
  230.     list->last = llast->next;
  231. }
  232.  
  233. /* remove a node from a linked list */
  234.  
  235. vptr remnode(list, nd)        /**/
  236. Lklist list;
  237. Lknode nd;
  238. {
  239.     vptr dat;
  240.  
  241.     nd->last->next = nd->next;
  242.     if (nd->next)
  243.     nd->next->last = nd->last;
  244.     else
  245.     list->last = nd->last;
  246.     dat = nd->dat;
  247.     zfree(nd, sizeof(struct lknode));
  248.     return dat;
  249. }
  250.  
  251. /* remove a node from a linked list */
  252.  
  253. vptr uremnode(list, nd)        /**/
  254. Lklist list;
  255. Lknode nd;
  256. {
  257.     vptr dat;
  258.  
  259.     nd->last->next = nd->next;
  260.     if (nd->next)
  261.     nd->next->last = nd->last;
  262.     else
  263.     list->last = nd->last;
  264.     dat = nd->dat;
  265.     return dat;
  266. }
  267.  
  268. /* delete a character in a string */
  269.  
  270. void chuck(str)            /**/
  271. char *str;
  272. {
  273.     while ((str[0] = str[1]))
  274.     str++;
  275. }
  276.  
  277. /* get top node in a linked list */
  278.  
  279. vptr getnode(list)        /**/
  280. Lklist list;
  281. {
  282.     vptr dat;
  283.     Lknode node = list->first;
  284.  
  285.     if (!node)
  286.     return NULL;
  287.     dat = node->dat;
  288.     list->first = node->next;
  289.     if (node->next)
  290.     node->next->last = (Lknode) list;
  291.     else
  292.     list->last = (Lknode) list;
  293.     zfree(node, sizeof(struct lknode));
  294.     return dat;
  295. }
  296.  
  297. /* get top node in a linked list without freeing */
  298.  
  299. vptr ugetnode(list)        /**/
  300. Lklist list;
  301. {
  302.     vptr dat;
  303.     Lknode node = list->first;
  304.  
  305.     if (!node)
  306.     return NULL;
  307.     dat = node->dat;
  308.     list->first = node->next;
  309.     if (node->next)
  310.     node->next->last = (Lknode) list;
  311.     else
  312.     list->last = (Lknode) list;
  313.     return dat;
  314. }
  315.  
  316. void freetable(tab, freefunc)    /**/
  317. Lklist tab;
  318. FFunc freefunc;
  319. {
  320.     Lknode node = tab->first, next;
  321.  
  322.     while (node) {
  323.     next = node->next;
  324.     if (freefunc)
  325.         freefunc(node->dat);
  326.     zfree(node, sizeof(struct lknode));
  327.     node = next;
  328.     }
  329.     zfree(tab, sizeof(struct lklist));
  330. }
  331.  
  332. char *ztrstr(s, t)        /**/
  333. char *s;
  334. char *t;
  335. {
  336.     char *p1, *p2;
  337.  
  338.     for (; *s; s++) {
  339.     for (p1 = s, p2 = t; *p2; p1++, p2++)
  340.         if (*p1 != *p2)
  341.         break;
  342.     if (!*p2)
  343.         return (char *)s;
  344.     }
  345.     return NULL;
  346. }
  347.  
  348. /* insert a list in another list */
  349.  
  350. void inslist(l, where, x)    /**/
  351. Lklist l;
  352. Lknode where;
  353. Lklist x;
  354. {
  355.     Lknode nx = where->next;
  356.  
  357.     if (!l->first)
  358.     return;
  359.     where->next = l->first;
  360.     l->last->next = nx;
  361.     l->first->last = where;
  362.     if (nx)
  363.     nx->last = l->last;
  364.     else
  365.     x->last = l->last;
  366. }
  367.  
  368. int countnodes(x)        /**/
  369. Lklist x;
  370. {
  371.     Lknode y;
  372.     int ct = 0;
  373.  
  374.     for (y = firstnode(x); y; incnode(y), ct++);
  375.     return ct;
  376. }
  377.